package com.zhouhong;

/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description: 二分查找
 * @Author: zhouhong
 * @Create: 2021-04-07 23:01
 **/

public class BinarySearch {
    private BinarySearch(){}
    // 一、递归实现
    public int search(int[] nums, int target){
        return search(nums, 0, nums.length - 1,target);
    }
    private int search(int[] arr, int l, int r, int target){
        if (l > r){
            return -1;
        }else {
            int mid = l + (r - l) / 2;
            if (arr[mid] == target){
                return mid;
            }
            if (arr[mid] < target){
                return search(arr, mid + 1, r, target);
            }
            return search(arr, l, mid - 1, target);
        }
    }

    // 非递归实现
    public int searchR(int[] nums, int target){
        int l = 0, r = nums.length - 1;
        while (l <= r){
            int mid = l + (r - l) / 2;
            if (nums[mid] == target){
                return mid;
            }
            if (nums[mid] < target){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return -1;
    }

    // 循环不变量改变
    public int searchR1(int[] nums, int target){
        int l = 0, r = nums.length;
        while (l < r){
            int mid = l + (r - l) / 2;
            if (nums[mid] == target){
                return mid;
            }
            if (nums[mid] < target){
                l = mid + 1;
            }else {
                r = mid;
            }
        }
        return -1;
    }


}
